/* The Computer Language Benchmarks Game
   适配Kotlin/Native的修正版本
*/

object pidigits {
    internal const val L = 10

    fun run(n: Int) {
        var remaining = n
        var j = 10
        val digits = PiDigitSpigot()

        while (remaining > 0) {
            val batchSize = minOf(remaining, L)
            val sb = StringBuilder()
            for (i in 0 until batchSize) {
                sb.append(digits.next())
            }
            // 不足L位时补空格
            if (batchSize < L) {
                sb.append(" ".repeat(L - batchSize))
            }
            sb.append("\t:$j\n")
            print(sb.toString())
            j += batchSize
            remaining -= batchSize
        }
    }
}

internal class PiDigitSpigot {
    var z: Transformation
    var x: Transformation
    var inverse: Transformation

    init {
        z = Transformation(1, 0, 0, 1)
        x = Transformation(0, 0, 0, 0)
        inverse = Transformation(0, 0, 0, 0)
    }

    fun next(): Int {
        val y = digit()
        if (isSafe(y)) {
            z = produce(y)
            return y
        } else {
            z = consume(x.next())
            return next()
        }
    }

    private fun digit(): Int = z.extract(3)
    private fun isSafe(digit: Int): Boolean = digit == z.extract(4)
    private fun produce(i: Int): Transformation = inverse.qrst(10, -10 * i, 0, 1).compose(z)
    private fun consume(a: Transformation): Transformation = z.compose(a)
}

// 优化的BigInt实现（使用LongArray存储数字，低位在前）
internal class BigInt private constructor(
    private val digits: LongArray, // 存储数字的每一位（基数10^9，低位在前）
    private val isNegative: Boolean
) {
    // 从Long创建
    constructor(value: Long) : this(
        when {
            value == 0L -> longArrayOf()
            value > 0 -> {
                val list = mutableListOf<Long>()
                var num = value
                while (num > 0) {
                    list.add(num % 1000_000_000)
                    num /= 1000_000_000
                }
                list.toLongArray()
            }
            else -> {
                val absValue = BigInt(-value).negate().digits
                absValue
            }
        },
        value < 0
    )

    // 从Int创建
    constructor(value: Int) : this(value.toLong())

    // 加法
    operator fun plus(other: BigInt): BigInt {
        if (this.isNegative != other.isNegative) {
            return if (this.isNegative) other.minus(this.negate()) else this.minus(other.negate())
        }
        val maxLen = maxOf(digits.size, other.digits.size)
        val result = LongArray(maxLen + 1)
        var carry = 0L
        for (i in 0 until maxLen) {
            val a = if (i < digits.size) digits[i] else 0L
            val b = if (i < other.digits.size) other.digits[i] else 0L
            val sum = a + b + carry
            result[i] = sum % 1000_000_000
            carry = sum / 1000_000_000
        }
        if (carry > 0) result[maxLen] = carry
        return BigInt(trimZeros(result), isNegative)
    }

    // 减法（this >= other，且符号相同）
    operator fun minus(other: BigInt): BigInt {
        if (this.isNegative != other.isNegative) {
            return this.plus(other.negate())
        }
        if (this < other) {
            return other.minus(this).negate()
        }
        val maxLen = maxOf(digits.size, other.digits.size)
        val result = LongArray(maxLen)
        var borrow = 0L
        for (i in 0 until maxLen) {
            val a = if (i < digits.size) digits[i] else 0L
            val b = if (i < other.digits.size) other.digits[i] else 0L
            var diff = a - b - borrow
            if (diff < 0) {
                diff += 1000_000_000
                borrow = 1L
            } else {
                borrow = 0L
            }
            result[i] = diff
        }
        return BigInt(trimZeros(result), isNegative)
    }

    // 乘法
    operator fun times(other: BigInt): BigInt {
        if (this.isZero() || other.isZero()) return BigInt(0)
        val result = LongArray(digits.size + other.digits.size)
        for (i in digits.indices) {
            var carry = 0L
            for (j in other.digits.indices) {
                val product = digits[i] * other.digits[j] + result[i + j] + carry
                result[i + j] = product % 1000_000_000
                carry = product / 1000_000_000
            }
            if (carry > 0) {
                result[i + other.digits.size] += carry
            }
        }
        return BigInt(trimZeros(result), isNegative xor other.isNegative)
    }

    // 除法（this / other，只返回整数部分）
    fun divide(other: BigInt): BigInt {
        if (other.isZero()) throw ArithmeticException("Division by zero")
        if (this < other) return BigInt(0)

        var remainder = this.copy()
        val quotient = mutableListOf<Long>()
        var shift = 0
        // 找到最大的shift，使other * 10^shift <= remainder
        while (other.shiftLeft(shift) <= remainder) {
            shift++
        }
        shift--

        while (shift >= 0) {
            val divisor = other.shiftLeft(shift)
            var count = 0L
            while (remainder >= divisor) {
                remainder -= divisor
                count++
            }
            quotient.add(count)
            shift--
        }
        // 商的 digits 是 quotient 的反转（因为我们从高位开始计算）
        quotient.reverse()
        return BigInt(trimZeros(quotient.toLongArray()), isNegative xor other.isNegative)
    }

    // 比较运算符
    operator fun compareTo(other: BigInt): Int {
        if (isNegative != other.isNegative) {
            return if (isNegative) -1 else 1
        }
        if (digits.size != other.digits.size) {
            return if (isNegative) {
                other.digits.size.compareTo(digits.size)
            } else {
                digits.size.compareTo(other.digits.size)
            }
        }
        // 从高位到低位比较
        for (i in digits.indices.reversed()) {
            val a = digits[i]
            val b = other.digits[i]
            if (a != b) {
                return if (isNegative) {
                    b.compareTo(a)
                } else {
                    a.compareTo(b)
                }
            }
        }
        return 0
    }

    // 取反
    fun negate(): BigInt = BigInt(digits.copyOf(), !isNegative)

    // 左移（乘以10^shift，用于除法优化）
    private fun shiftLeft(shift: Int): BigInt {
        if (shift <= 0) return this.copy()
        val newDigits = LongArray(digits.size + shift)
        digits.copyInto(newDigits, shift, 0, digits.size)
        return BigInt(newDigits, isNegative)
    }

    // 复制
    private fun copy(): BigInt = BigInt(digits.copyOf(), isNegative)

    // 检查是否为0
    fun isZero(): Boolean = digits.isEmpty() || (digits.size == 1 && digits[0] == 0L)

    // 移除末尾的0
    private fun trimZeros(arr: LongArray): LongArray {
        var lastNonZero = arr.lastIndex
        while (lastNonZero >= 0 && arr[lastNonZero] == 0L) {
            lastNonZero--
        }
        return if (lastNonZero < 0) longArrayOf() else arr.copyOf(lastNonZero + 1)
    }

    // 转换为Int（仅用于小数字）
    fun toInt(): Int {
        if (digits.size > 1) throw ArithmeticException("Value too large for Int")
        return if (digits.isEmpty()) 0 else (digits[0].toInt() * if (isNegative) -1 else 1)
    }

    // 辅助函数：将数字格式化为9位，不足补前导零
    private fun format9Digits(num: Long): String {
        val str = num.toString()
        return if (str.length < 9) "0".repeat(9 - str.length) + str else str
    }

    override fun toString(): String {
        if (isZero()) return "0"
        val sb = StringBuilder()
        if (isNegative) sb.append('-')
        // 从高位到低位添加
        for (i in digits.indices.reversed()) {
            val d = digits[i]
            if (i != digits.lastIndex) {
                sb.append(format9Digits(d))
            } else {
                sb.append(d)
            }
        }
        return sb.toString()
    }
}

internal class Transformation {
    var q: BigInt
    var r: BigInt
    var s: BigInt
    var t: BigInt
    var k: Int = 0

    constructor(q: Int, r: Int, s: Int, t: Int) {
        this.q = BigInt(q)
        this.r = BigInt(r)
        this.s = BigInt(s)
        this.t = BigInt(t)
        k = 0
    }

    constructor(q: BigInt, r: BigInt, s: BigInt, t: BigInt) {
        this.q = q
        this.r = r
        this.s = s
        this.t = t
        k = 0
    }

    fun next(): Transformation {
        k++
        q = BigInt(k)
        r = BigInt(4 * k + 2)
        s = BigInt(0)
        t = BigInt(2 * k + 1)
        return this
    }

    fun extract(j: Int): Int {
        val bigj = BigInt(j)
        val numerator = q * bigj + r
        val denominator = s * bigj + t
        return numerator.divide(denominator).toInt()
    }

    fun qrst(q: Int, r: Int, s: Int, t: Int): Transformation {
        this.q = BigInt(q)
        this.r = BigInt(r)
        this.s = BigInt(s)
        this.t = BigInt(t)
        k = 0
        return this
    }

    fun compose(a: Transformation): Transformation {
        return Transformation(
            q * a.q,
            q * a.r + r * a.t,
            s * a.q + t * a.s,
            s * a.r + t * a.t
        )
    }
}

// 入口函数：先测试小位数（如10位），快速验证
fun main(args: Array<String>) {
    val n = if (args.isNotEmpty()) args[0].toInt() else 1000 // 默认为10位，加快测试
    pidigits.run(n)
}
